package FloodFill;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-02
 */
public class 魔法棒 {
    static boolean[][] visited = new boolean[100][100];

    static int fill(int[][] image, int x, int y, int origColor, int newColor) {
        // 出界：超出数组边界
        if (!inArea(image, x, y)) return 1;
        // 碰壁：遇到其他颜⾊，超出 origColor 区域
        if (image[x][y] != origColor) return 0;
        // 已探索过的 origColor 区域
        //因为会被替换成新颜色newColor,也是被访问过，原来是origColor,所以返回1
        if (visited[x][y]) return 1;
        visited[x][y] = true;
        int surround =
                fill(image, x - 1, y, origColor, newColor) +
                        fill(image, x + 1, y, origColor, newColor) +
                        fill(image, x, y - 1, origColor, newColor) +
                        fill(image, x, y + 1, origColor, newColor);
        if (surround < 4) image[x][y] = newColor;
        return 1;
    }

    static boolean inArea(int[][] image, int x, int y) {
        return x >= 0 && x < image.length && y >= 0 && y < image[0].length;
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 1, 1},
                       {1, 0, 0},
                       {1, 0, 1}};
        fill(arr,
                1, 1, 1, 2);
        System.out.println(arr);

    }
}
